/*
 * One example for NOI CSP-J Lesson 8:
 * <https://courses.fmsoft.cn/plzs/noijunior-other-data-structures.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

// 返回可被放入容量为 W 的背包中的最大价值。
int knapsack(int W, vector<int> &val, vector<int> &wt) {
    int n = wt.size();

    // 初始化一个 dp 表：(n + 1) 行、(W + 1) 列
    vector<vector<int>> dp(n + 1, vector<int>(W + 1));

    // 从底向上构造 dp[][] 表
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= W; j++) {

            // If there is no item or the knapsack's capacity is 0
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else {
                int pick = 0;

                // 如果第 i 个物品不超过背包的容量，则选择该物品。
                if (wt[i - 1] <= j)
                    pick = val[i - 1] + dp[i - 1][j - wt[i - 1]];

                // 计算不选择该物品时，得到的价值。
                int notPick = dp[i - 1][j];

                // dp[i][j] 中保存的便是有 i 个物品，容量为 j 的情形下的解
                dp[i][j] = max(pick, notPick);
            }
        }
    }

    return dp[n][W];
}

int main() {
    vector<int> val = {1, 2, 3};
    vector<int> wt = {4, 5, 1};
    int W = 4;

    cout << knapsack(W, val, wt) << endl;
    return 0;
}
